package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/longest-palindromic-substring/
 *  最长的回文字串 动归
 * author: hongchen.liao
 * date:  2022/9/27
 */
public class _5_ {
    class Solution {
        public String longestPalindrome(String s) {
            int slen = s.length();
            boolean[][] dp = new boolean[slen][slen];
            for(int i = 0; i < slen; i++){
                dp[i][i] = true;
            }
            char[] cs = s.toCharArray();
            int begin = 0, maxLen = 1;
            for(int j = 1; j < slen; j++){
                for(int i = 0; i < j; i++){
                    if(cs[i] != cs[j]){
                        dp[i][j] = false;
                    }else{
                        if(j - i < 3){
                            dp[i][j] = true;
                        }else{
                            dp[i][j] = dp[i+1][j-1];
                        }
                        if(dp[i][j] && j-i+1 > maxLen){
                            begin = i;
                            maxLen = j-i+1;
                        }
                    }
                }
            }
            return s.substring(begin, begin+maxLen);
        }
    }


}
